package sort.折半插入排序;


public class InsertSort1 {

    public static void test() {
        int[] data = new int[]{-23,45,2,-45,9,5,3,65,-24};
        sort(data);
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }
    public static void sort(int[] data){
        int low,hight,mid;
        int tmp;//备份存储待插入的值
        for (int i = 1; i < data.length; i++) {
            if(data[i]<data[i-1]){
                tmp = data[i];
                low = 0;
                hight = i-1;
                while(low<=hight){
                    mid = (low+hight)/2;
                    if(data[mid]<=tmp){  //当中间值小于等于待插入的值，搜索[mid+1,hight]区间
                        low = mid +1;
                    }else{
                        hight = mid - 1; //当中间值小于等于待插入的值,搜索[low,mid-1]区间
                    }
                }
                //将[low,i-1]区间的值后移动
                for (int j = i-1; j >= low; j--) {
                    data[j+1] = data[j];
                }
                //待插入的值插入
                data[low] =tmp;
            }
        }
    }
}
